package trees;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

;

public class TreeStructure {

	public static final String LEFT = "left";
	public static final String RIGHT = "right";
	public static final String SPACE = "    ";
	public static final String NEW_LINE = "\n";

	static class Tree {

		int value;
		Tree left, right;

		public Tree(int v) {
			this.value = v;
		}

	}
	
	public static int traverse(Tree t) {
		
		int depth = 0;
		if (t != null) {
			depth = 1;
			int d1 = traverse(t.left);
			int d2 = traverse(t.right);

			depth += d1 > d2 ? d1 : d2;
		}
		
		return depth;
	}

	public static int getTreeDepth(Tree t) {

		int depth = 0;
		if (t != null) {

			int d1 = traverse(t.left);
			int d2 = traverse(t.right);

			depth += d1 > d2 ? d1 : d2;
		}
		return depth;
	}

	public static void printTreeAccordingToTheirLevel(Tree t) {

		Map<Integer, LinkedList<String>> map = new HashMap<Integer, LinkedList<String>>();
		int depth = getTreeDepth(t);
		traverse(t, map, depth);
		
		print(map, depth);

	}

	private static void print(Map<Integer, LinkedList<String>> map, int depth) {
		
		System.out.println();
		int initialSpaceSize = (int)Math.pow(2, depth);
		for(int i=depth; i>=0; i--) {
			LinkedList<String> list = map.get(i);
			while (!list.isEmpty()) {
				String s = list.removeFirst();
				printSpace(initialSpaceSize);
				if (s != null) {
					System.out.print(s);
				} else {
					System.out.print(SPACE);
				}
			}
			initialSpaceSize = ((depth + 2 - i) * initialSpaceSize - 1) / (depth + 3 - i);
			System.out.print(NEW_LINE);
			
		}
	}

	private static void printSpace(int d) {
		for (int i=0; i<d; i++) {
			System.out.print(SPACE);
		}
	}

	private static void traverse(Tree t, Map<Integer, LinkedList<String>> map,
			int depth) {

		if (depth >= 0) {

			LinkedList<String> list = map.get(depth);
			if (list == null) {
				list = new LinkedList<String>();
			}
			if (t != null) {
				list.addLast(String.valueOf(t.value));
				traverse(t.left, map, depth -1);
				traverse(t.right, map, depth -1);
				
			} else {
				list.addLast(null);
				traverse(null, map, depth -1);
				traverse(null, map, depth -1);
			}
			map.put(depth, list);
		}

	}

	public static boolean areStructurallyTheSame(Tree t1, Tree t2) {

		return getTreeStructure(t1).equals(getTreeStructure(t2));

	}

	public static String getTreeStructure(Tree t) {

		String outputString = null;
		if (t == null) {
			outputString = "";
		} else {
			StringBuilder sb = new StringBuilder();
			sb.append(LEFT);
			sb.append(getTreeStructure(t.left));
			sb.append(LEFT);
			sb.append(getTreeStructure(t.right));

			outputString = sb.toString();
		}

		return outputString;
	}

	public static void main(String[] args) {

		Tree t1 = new Tree(7);
		Tree t2 = new Tree(5);
		Tree t3 = new Tree(10);
		t1.left = t2;
		t1.right = t3;
		Tree t4 = new Tree(3);
		Tree t5 = new Tree(15);
		t2.left = t4;
		t3.right = t5;
		Tree t6 = new Tree(1);
		Tree t7 = new Tree(4);
		t4.left = t6;
		t4.right = t7;

		Tree t11 = new Tree(17);
		Tree t12 = new Tree(15);
		Tree t13 = new Tree(110);
		t11.left = t12;
		t11.right = t13;
		Tree t14 = new Tree(13);
		Tree t15 = new Tree(115);
		t12.left = t14;
		t13.right = t15;
		Tree t16 = new Tree(11);
		Tree t17 = new Tree(14);
		t14.left = t16;
		t14.right = t17;
		
		printTreeAccordingToTheirLevel(t1);

		System.out.println(areStructurallyTheSame(t1, t12));

		System.out.println(getTreeDepth(t1));
		System.out.println(getTreeDepth(t2));
		System.out.println(getTreeDepth(t3));
		
	}

}
